package leetcode_1100;

/**
 *@author 周杨 
 *BestSightseeingPair_1021 返回一个数组里 A[i]+A[j]+i-j最大的组合 其中j>
 *describe:动态规划
 *2019年3月24日 上午11:33
 */
public class BestSightseeingPair_1021 {
	public static void main(String[] args) {
		BestSightseeingPair_1021 test = new BestSightseeingPair_1021();
		System.out.println(test.maxScoreSightseeingPair(new int[] {8,1,5,2,6}));
	}
	public int maxScoreSightseeingPair(int[] A) {
        int dp = 0,max = Integer.MIN_VALUE;
        for(int i=1;i<A.length;++i) {
        	max = Math.max(max, A[i]+A[dp]+dp-i);
        	if(A[dp]-A[i] < i-dp) {
        		dp = i;
        	}
        }
        return max;
    }
}
